Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 4 на тему: "Структура даних ЧЕРГА " з дисципліни: " Програмування. Частина III. Структуриданих та алгоритми " Вибір індивідуального завдання: №варіанта=(11+97)%30+1=19  Львів – 2012 МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудовичерги, дослідження динаміки його вмісту та використання черг для розв'язання прикладних задач. ПОСТАНОВКА ЗАДАЧІ Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Написати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow). 19. Змоделювати дек, в якому до опису деку додано функцію change, яка міняє значення елементів, що знаходяться в лівому та в правому кінцях деку. Кожний раз, коли у вхідній послідовності зустрінеться число 0, то треба обміняти значення лівого і правого кінців деку. Після обробки всієї заданої вхідної послідовності знайти суму парних чисел деку.   ДИНАМІКА ВМІСТУ ЧЕРГИ Послідовність K цілих (додатніх, від'ємних, нульових, парних і непарних) чисел Моя послідовність: 1 2 3 4 5 -1 0 3 4 5 2 1 Схематичне зображення черги після обробки кожного числа з вхідної послідовності Введемо такі позначення: П – покажчик початку черги, К – покажчик кінця черги К П            -queue(); П К 1            -push_left(1); П К 1 2           - push_right(2); П К 3 1 2          - push_left(3); П К 3 1 2 4         - push_right(4); П К 5 3 1 2 4        - push_left(5); П К 3 1 2 4        - pop(); П К 4 1 2 3        - change(); П К 3 4 1 2 3       - push_left(3); П К 3 4 1 2 3 4      - push_right(4); П К 5 3 4 1 2 3 4     - push_left(5); П К 5 3 4 1 2 3 4 2    - push_right(2); П К 1 5 3 4 1 2 3 4 2   - push_left(1); Визначити суму парних елементів деку. Сума парних елементів деку рівна 12. АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ Створюємо клас queue1.h Під час реалізації програми вводимо послідовність чисел. Якщо число непарне, то вводимо в ліву сторону черги, якщо парне – в праву. При вводі від’ємного числа ми вилучаємо 1-й елемент черги. При вводі 0, ми міняємо лівий і правий елемент місцями. Виводимо результуючу чергу. Виводимо суму парних чисел. Завершуємо роботу програми. РЕЗУЛЬТАТИ ВИКОНАННЯ ПРОГРАММИ Скріншот 1: Меню програми.
Скріншот 2: Ввід натуральних чисел.
Скріншот 3: Вивід результуючої черги.
Скріншот 4: Сума парних чисел.
ВИСНОВКИ На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних – чергу. Набувпрактичних навичок побудови черги та провів дослідження динаміки її вмісту. ДОДАТКИ queue1.h #ifndef MAIN_SAVITCH_QUEUE1_H #define MAIN_SAVITCH_QUEUE1_H #include <cstdlib> // Provides size_t #include <cassert> // Надає макрос assert. #include <con...